package LeetCode._02算法基础.day14动态规划;

/**
 * @author 挚爱之夕
 * @version 中等
 * @implSpec 给你一个字符串 s，找到 s 中最长的回文子串。
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * @since 2022 - 09 - 10 - 10:18
 */
public class _5最长回文串 {
    public static void main(String[] args) {
        String s = "babad";
        System.out.println(longestPalindrome(s));
    }
    //by me 枚举窗口
    public static String longestPalindrome(String s) {
        for(int len = s.length(); len >= 1; len--){
            for(int i = 0; i + len <= s.length(); i++){
                if(isPalindrome(s, i, i + len - 1)){
                    return s.substring(i, i + len);
                }
            }
        }
        return null;
    }
    public static boolean isPalindrome(String s, int start, int end){
        int l = start, r = end;
        while(l < r){
            if(s.charAt(l++) != s.charAt(r--)){
                return false;
            }
        }
        return true;
    }
    //官方思路 动态规划
    public static String longestPalindrome1(String s) {
        int len = s.length();
        if(len < 2)
            return s;

        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i < len; i++) dp[i][i] = true;
        char[] charArray = s.toCharArray();
        int maxLen = 1, start = 0;
        for(int L = 2; L <= len; L++){  //从长度2开始递推
            for(int i = 0; i + L <= len; i++){  //起始索引
                int j = i + L - 1;  //结束索引
                if(charArray[i] != charArray[j]){   //两端字母不相同
                    dp[i][j] = false;
                }else{
                    if(L <= 3)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];    //递推公式
                    if(dp[i][j] && L > maxLen){ //记录最大回文串起始索引索引和长度
                        maxLen = L;
                        start = i;
                    }
                }
            }
        }
        return s.substring(start, maxLen + start);
    }
}
